package com.job.kujiale;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 *
 * </p>
 *
 * @author 12071
 * @date 2022/10/10 16:13
 */
public class A2 {

    public static void main(String[] args) {

    }

    class Node{
        Node left;
        Node right;

        Node(Node left, Node right){
            this.left = left;
            this.right = right;
        }
    }

    public static int minDepth(Node root){
        if(root==null) return 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int depth = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                if(node.left==null && node.right==null) return depth;
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }
            depth++;
        }
        return depth;
    }

    public static int minDepth2(Node root){
        if(root==null) return 0;
        return Math.min(minDepth2(root.left),minDepth2(root.right)) +1;
    }
}
